﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class AnagramsByStack
    {
        private char[] input;
        private char[] output;
        int count = 0;
        public AnagramsByStack()
        {
            int testCase = GetConsole.GetInt();
            while (testCase-- > 0)
            {
                count = 0;
                input = GetConsole.GetString().ToCharArray();
                output = GetConsole.GetString().ToCharArray();
                Stack<char> stack = new Stack<char>();
                MakeWord(0, 0, stack, string.Empty);
                Console.WriteLine(count);
            }
        }
        private void MakeWord(int inIndex, int outIndex, Stack<char> stack, string io)
        {
            if (outIndex == output.Length)
            {
                count++;
                Console.WriteLine(io);
                return;
            }
            if (stack.Count > 0 && stack.Peek() == output[outIndex])
            {
                char[] buffer = new char[stack.Count];
                stack.CopyTo(buffer, 0);
                Stack<char> newStack = new Stack<char>(buffer.Reverse());
                newStack.Pop();
                MakeWord(inIndex, outIndex + 1, newStack, io + "o ");
            }
            for (int i = inIndex; i < input.Length; i++)
            {
                if (input[i] == output[outIndex])
                {
                    char[] buffer = new char[stack.Count];
                    stack.CopyTo(buffer, 0);
                    Stack<char> newStack = new Stack<char>(buffer.Reverse());
                    MakeWord(i + 1, outIndex + 1, newStack, io + "i o ");
                }
                io += "i ";
                stack.Push(input[i]);
            }
         }
    }
}
